#pragma once

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;
/*HJJ QQ479287006
 *给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

 

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：

输入：lists = []
输出：[]
示例 3：

输入：lists = [[]]
输出：[]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 这道题分治基本全抄的
 * */

//特别是这个递归合并 自己看一下
ListNode *onceMerge(ListNode *list1, ListNode *list2) {
    ListNode *head = nullptr;

    if (list1 == nullptr && list2 == nullptr)
        return nullptr;
    if (list1 == nullptr)
        return list2;
    if (list2 == nullptr)
        return list1;

    if (list1->val <= list2->val) {
        head = list1;
        head->next = onceMerge(list1->next, list2);

    } else {
        head = list2;
        head->next = onceMerge(list1, list2->next);
    }


    return head;

}

ListNode *mergeFenzhi(vector<ListNode *> &lists, int left, int right) {
    if (left == right)
        return lists[left];


    int mid = left + (right - left) / 2;
    ListNode *l1 = mergeFenzhi(lists, left, mid);
    ListNode *l2 = mergeFenzhi(lists, mid + 1, right);
    return onceMerge(l1, l2);//这个return 之后返回到别的call里面的作为一个返回的结果 然后继续合并




}


/* 分治两两合并*/
ListNode *mergeKLists(vector<ListNode *> &lists) {


    if (lists.size() == 0)
        return nullptr;
    if (lists.size() == 1)
        return lists[0];
    if (lists.size() == 2)
        return onceMerge(lists[0], lists[1]);


    return mergeFenzhi(lists, 0, lists.size() - 1);

}